今天休息一下暫停物件導向系列，來説說搜尋。
搜尋要有資料嘛，而資料有分兩種：
一種是有索引（index）的資料，例如章節、目錄，索引結構包含Binary Search Tree、B tree、Hash table等等。
另一種是沒有索引，直接在檔案或符號裡搜尋，稱為在循序結構上搜尋資料，就是今天要聊的部分。

在此介紹兩種簡單的搜尋大法:

Linear Search

循序搜尋，又稱線性搜尋，如其名循序一個接著一個搜下去，通常用在沒有排序過的檔案，有幾筆資料就搜索幾次，因此不適合大量資料時使用。
例如有100萬筆資料，最糟的可能是要搜尋一百萬遍（目標在最後一個），時間複雜度為O(N)。

    int linearSearch(){
        int i;
        for(i = 0; i < n; i++){
            if(a[i] == key)
            return(i);
        }
        
     return -1;
}

完整程式範例：

#include <iostream>

using namespace std;
int search(int arr[], int f){
    int i;
    for(i =0; i < 6;i++){
        if(arr[i] == f){
            return i;
        }
    }return -1;
    
}
int main()
{
    int arr[] = {2,11,7,1,9,5,8};
    int result;
    search(arr,0);
    if(result == -1){
        cout << "Not Found" << endl;
    }else cout << "Number Found"  <<endl;
    return 0;
}

Binary Search

只能用在已經排序過(sorted)的資料！ ，由小到大排序好。

因為是利用把資料對切一半，找出可能的範圍藉此縮短搜尋時間的方法。
如果全部不照大小排好，對切法無法達成效果，請看以下。

例如有一串數字，1,2,3,4,5,6,7,8,9,10，我們想找到數字3是否在這個裡面，linear search會從1 -> 2 ....10，直到找到目標或是到底為止。
而binary search是這樣用的:

1. 把10切一半，10/2 = 5，所以會有兩半，左邊有1,2,3,4，右邊有6,7,8,9,10
2. 看看目標物3在哪半邊，發現在左邊，
3. 那把左邊的那半再切一半，左邊1,2 右邊3,4
4. 右邊3,4切一半，找到3。

用程式翻譯如下：
注：int m 是middle中間的意思，left和right如上是左邊右邊，target是要搜尋的值，n是指sizeof(array) / sizeof(array[0]);

int BinarySearch(int array[], int n, int target){
    int left = 0; right = n-1, m;
    while(left <= right){
        m = (1eft + right )/2;
        if(target == array[m]){
            return(m);
        if(target > array[m]){
            left = m + 1;
        }else 
            right = m - 1;
    }
    return -1; 
}
    }

完整程式碼：

#include <iostream>

using namespace std;
int BinarySearch(int array[], int n, int target){
    int left = 0, right = n-1, m;
    while(left <= right){
        m = (left + right )/2;
        if(target == array[m])
            return(m);
        if(target > array[m])
            left = m + 1;
        else 
            right = m - 1;
    }
    return -1; 
}

int main(){
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int result = BinarySearch(array, n, 7);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);

}

注：printf跟cout都是輸出的意思

Reference: Geeksforgeeks, cplusplus, programiz